/*
day105
2019.12.11
*/
#include<vector>
#include<iostream>
using namespace std;

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
	{
        int i=0,j=0,tem=0;
        vector<int> vec=nums1;
        while(i<m && j<n)
        {
        	if(i<m && j<n && nums1[i]<=nums2[j])
        	{
        		vec[tem]=nums1[i];
        		tem++;
        		i++;
			}
			
			if(i<m && j<n && nums1[i]>=nums2[j])
        	{
        		vec[tem]=nums2[j];
        		tem++;
        		j++;
			}
		}
		while(i<m)
		{
			vec[tem]=nums1[i];
        	tem++;
        	i++;
		}
		
		while(j<n)
		{
			vec[tem]=nums2[j];
        	tem++;
        	j++;
		}
		
		nums1=vec;
    }

	
	void merge1(vector<int>& nums1, int m, vector<int>& nums2, int n) 
	{
		int i=m-1,j=n-1;
		int tem=m+n-1;
		while(i>=0 && j>=0)
		{
			if(i>=0 && j>=0 && nums1[i]>=nums2[j])
			{
				nums1[tem]=nums1[i];
				tem--;
				i--;
			}
			
			if(i>=0 && j>=0 && nums1[i]<=nums2[j])
			{
				nums1[tem]=nums2[j];
				tem--;
				j--;
			}
		}
		
		while(i>=0)
		{
			nums1[tem] =nums1[i];
			tem--;
			i--; 
		}
			
		while(j>=0)
		{
			nums1[tem] =nums2[j];
			tem--;
			j--; 
		}
		 
	 } 

};



int main()
{
	vector<int> nums1={1,2,3,0,0,0};
	vector<int> nums2={2,5,6};
	int m=3,n=3;
	Solution s;
	s.merge1(nums1,m,nums2,n);
	for(int i=0;i<m+n;i++)
	{
		cout<<nums1[i]<<endl;
	}
	return 0;
}
